package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;

import java.util.*;
/**
 * <h1>简单寻路-DFS</h1>
 * 使用深度优先算法，构建的路径信息。
 * <p>
 *    这种方式只能保存一条路径。
 * </p>
 *
 *
 * @author longandai@163.com
 */
public  class DfsSimplePath<T> {
    private Graph<T> graph;
    //起点
    private Vertex<T> source;
    //记录可以到达的起点
    private Set<Vertex<T>> pathToContainer = new HashSet<>();
    //每个到达的起点，是通过哪个节点访问到的。这个只会保存最后记录到的数据
    //这个关系 把pathToContainer 的节点维护成了一个树。
    private Map<Vertex<T>, Vertex<T>> toParent = new HashMap<>();


    /**
     * 当前的{@code source}是否有路径可以到达{@code target}
     * @param target 目标
     * @return
     */
    public boolean hasPathTo(T target) {
        return pathToContainer.contains(Vertex.create(target));
    }

    /**
     * 返回路径信息.
     * <pre>
     *     核心思想：通过{@code toParent} 字段，向上循环查询，
     *
     * </pre>
     * @param target
     * @return
     */
    public  Iterable<T> pathTo(T target) {
        if(!hasPathTo(target)){
            return null;
        }
        Deque<T> result = new LinkedList<>();
        Vertex<T> cluster = Vertex.create(target);
        while(toParent.containsKey(cluster)){
            result.push(cluster.getKey());
            cluster = toParent.get(cluster);
        }
        result.push(source.getKey());
        return result;
    }


    /**
     * 从{@code source} 开始，进行dfs遍历，记录可以到达的
     */
    private void dfsAllPath(){
        Deque<Vertex<T>> deque = new LinkedList<>();
        deque.push(this.graph.getVertices().get(source));
        while(!deque.isEmpty()){
            Vertex<T> item = deque.pop();
            if(!pathToContainer.add(item)){
                continue;
            }
            item.getNext()
                    .stream()
                    .map(Edge::getTo)
                    .filter(next->!pathToContainer.contains(next))
                    .map(vertex -> {
                        //记录信息
                        toParent.put(vertex, item);
                        return (Vertex<T>)vertex;
                    })
                    .forEach(ver->{
                        deque.push((Vertex<T>)ver);
                    });
        }
    }


    private DfsSimplePath() {

    }

    private DfsSimplePath(Graph<T> graph,Vertex<T> source) {
        this.source = source;
        this.graph = graph;
        dfsAllPath();
    }
    public static final <TT>  DfsSimplePath<TT> create(Graph<TT> graph,Vertex<TT> source){
        return new DfsSimplePath(graph, source);
    }




}
